package modifyString;

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution {
    Queue<Character> queue = new ArrayDeque<>();
    public String modifyString(String s) {
        // 不包含任何连续重复的字符
        for (int i = 0; i < 26; i++) {
            queue.add((char)(i+'a'));
        }
        char[] ans = s.toCharArray();
        int i = 0,j = 0;
        while (i<s.length()&&j<s.length()){
            if(!checkFirst(i,s)){
                i++;
            } else if (!checkLast(j,s)) {
                j++;
            } else {
                // 替换i和j之间的单词
                swap(ans,i,j);
                i++;
                j++;
            }
        }
        return new String(ans);
    }
    private void swap(char[] chars,int i,int j) {
        // 替换掉i和j之间的所有元素 并且保证不含重复元素
        // 也就是说 首部和尾部不能是相同的单词 其它可以是任何单词
        for (int k = i; k <= j; k++) {
            char prev = ' ';
            if(k>0)prev = chars[k-1];
            char next = ' ';
            if(k<chars.length-1) next = chars[k+1];
            while (true) {
                if(queue.peek()!=next&&queue.peek()!=prev){
                    chars[k] = queue.peek();
                    break;
                }
                queue.add(queue.poll());
            }
        }
    }
    // 判断是不是问好的尾部
    private boolean checkLast(int i,String s) {
        if(i == s.length()-1) return s.charAt(i) =='?';
        return s.charAt(i) == '?'&&s.charAt(i+1)!='?';
    }

    private boolean checkFirst(int i,String s){
        if(i == 0) return s.charAt(i) == '?';
        return s.charAt(i) == '?'&&s.charAt(i-1) !='?';
    }
}
